package com.fps.webshop.question.question0100_0199;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.fps.webshop.question.common.TreeNode;

/**
 * 102. 二叉树的层序遍历
 * 
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * 
 * 示例：
 * 二叉树：[3,9,20,null,null,15,7],
 *     3
 *    / \
 *   9  20
 *     /  \
 *    15   7
 *    
 * 返回其层序遍历结果：
 * [
 *   [3],
 *   [9,20],
 *   [15,7]
 * ]
 */
public class Question102 {
	
	/**
	 * 第一次提交，使用两个队列进行记录每一层的数据
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.7 MB	Java	2021/08/23 10:41	
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了92.76%的用户
	 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了37.93%的用户
	 */
	public static List<List<Integer>> levelOrder1(TreeNode root) {
		List<List<Integer>> topList = new ArrayList<List<Integer>>();
		if (root == null) {
			return topList;
		}
		Queue<TreeNode> queueNow = new LinkedList<>();
		Queue<TreeNode> queueNext = new LinkedList<>();

		List<Integer> list1 = new ArrayList<Integer>();
		list1.add(root.val);
		topList.add(list1);

		if (root.left != null) {
			queueNext.offer(root.left);
		}
		if (root.right != null) {
			queueNext.offer(root.right);
		}

		while (!queueNext.isEmpty()) {
			List<Integer> list = new ArrayList<Integer>();
			queueNow = queueNext;
			queueNext = new LinkedList<>();
			while (!queueNow.isEmpty()) {
				TreeNode theNode = queueNow.poll();
				list.add(theNode.val);
				if (theNode.left != null) {
					queueNext.offer(theNode.left);
				}
				if (theNode.right != null) {
					queueNext.offer(theNode.right);
				}
			}
			topList.add(list);
		}
		return topList;
	}
	
	/**
	 * 第2次提交，依旧是两个队列进行记录每一层的数据，进行优化
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.5 MB	Java	2021/08/23 10:44	
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了92.76%的用户
	 * 内存消耗：38.5 MB, 在所有 Java 提交中击败了74.61%的用户
	 */
	public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> topList = new ArrayList<List<Integer>>();
		if (root == null) {
			return topList;
		}
		
		Queue<TreeNode> queueNext = new LinkedList<>();
		queueNext.offer(root);
		
		while (!queueNext.isEmpty()) {
			List<Integer> list = new ArrayList<Integer>();
			Queue<TreeNode> queueNow = queueNext;
			queueNext = new LinkedList<>();
			while (!queueNow.isEmpty()) {
				TreeNode theNode = queueNow.poll();
				list.add(theNode.val);
				if (theNode.left != null) {
					queueNext.offer(theNode.left);
				}
				if (theNode.right != null) {
					queueNext.offer(theNode.right);
				}
			}
			topList.add(list);
		}
		return topList;
    }
	
	/**
	 * 第3次提交，使用两个List记录，没什么改进
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.7 MB	Java	2021/08/23 10:48	
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了92.76%的用户
	 * 内存消耗：38.7 MB, 在所有 Java 提交中击败了37.93%的用户
	 */
	public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> topList = new ArrayList<List<Integer>>();
		if (root == null) {
			return topList;
		}
		
		List<TreeNode> queueNext = new ArrayList<>();
		queueNext.add(root);
		
		while (!queueNext.isEmpty()) {
			List<Integer> list = new ArrayList<Integer>();
			List<TreeNode> queueNow = queueNext;
			queueNext = new ArrayList<>();
			for (int i = 0;i< queueNow.size();i++) {
				TreeNode theNode = queueNow.get(i);
				list.add(theNode.val);
				if (theNode.left != null) {
					queueNext.add(theNode.left);
				}
				if (theNode.right != null) {
					queueNext.add(theNode.right);
				}
			}
			topList.add(list);
		}
		return topList;
    }
	
	/**
	 * 第4次提交，使用一个队列记录，中间使用上一层队列的数量来中断循环
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.6 MB	Java	2021/08/23 10:54	
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了92.76%的用户
	 * 内存消耗：38.6 MB, 在所有 Java 提交中击败了58.89%的用户
	 */
	public List<List<Integer>> levelOrder4(TreeNode root) {
		List<List<Integer>> topList = new ArrayList<List<Integer>>();
		if (root == null) {
			return topList;
		}
		
		Queue<TreeNode> queueNext = new LinkedList<>();
		queueNext.offer(root);
		
		while (!queueNext.isEmpty()) {
			List<Integer> list = new ArrayList<Integer>();
			int count = queueNext.size();
			while (count>0) {
				TreeNode theNode = queueNext.poll();
				count--;
				list.add(theNode.val);
				if (theNode.left != null) {
					queueNext.offer(theNode.left);
				}
				if (theNode.right != null) {
					queueNext.offer(theNode.right);
				}
			}
			topList.add(list);
		}
		return topList;
	}
	
	public static void main(String[] args) {
		TreeNode root = new TreeNode(41);
		TreeNode leftNode1 = new TreeNode(-57);
		TreeNode rightNode1 = new TreeNode(-57);
		root.left = leftNode1;
		root.right = rightNode1;
		
		TreeNode leftNode2 = new TreeNode(7);
		TreeNode rightNode2 = new TreeNode(67);
		leftNode1.right = rightNode2;
		leftNode1.left = leftNode2;
		
		TreeNode leftNode3 = new TreeNode(67);
		TreeNode rightNode3 = new TreeNode(55);
		rightNode1.left = leftNode3;
		rightNode1.right = rightNode3;
		
		for(List<Integer> list: levelOrder1(root)) {
			for(Integer a : list) {
				System.out.print(a+" ");
			}
			System.out.println();
		}
	}
}
